Randomized smoothing is one of the most promising techniques for adversarial training with guarantees. This work is likely to be very influential among people studying adversarial machine learning.

Randomized smoothing is a recently proposed defense against adversarial attacks that has achieved state-of-the-art provable robustness against \ell_2 perturbations. A number of works have extended the guarantees to other metrics, such as \ell_1 or \ell_\infty, by using different smoothing measures. Although the current framework has been shown to yield near-optimal \ell_p radii, the total safety region certified by the current framework can be arbitrarily small compared to the optimal. In this work, we propose a framework to improve the certified safety region for these smoothed classifiers without changing the underlying smoothing scheme. The theoretical contributions are as follows: 1) We generalize the certification for randomized smoothing by reformulating certified radius calculation as a nested optimization problem over a class of functions.